Welcome To My Blog

STACK

• Penyimpanan dan pengambilan data yang sangat efektif apabila data yang terakhir masuk adalah data yang akan diambil pertama kali.
• Tumpukan memungkinkan akses ke satu item data saja, yaitu item terakhir yang disisipkan.
• Bila kita menghilangkan item ini maka kita bisa mengakses ke sebelah item terakhir yang disisipkan, dan seterusnya.

SEJARAH
• Tumpukan pertama kali diusulkan pada tahun 1955, dan kemudian dipatenkan pada tahun 1957, oleh Friedrich L. Bauer Jerman.
• Konsep yang sama dikembangkan secara independen, pada sekitar waktu yang sama, oleh Leonard Charles Australia Hamblin.

PENGERTIAN
• Merupakan tumpukan data yang seolah-olah diletakkan di atas data yang lain.
• Kita dapat menambahkan (menyisipkan) data dan mengambil (menghapus) data melalui ujung yang sama, yang disebut sebagai ujung atas stack (top of stack).
• Stack bersifat LIFO (Last In First Out).
• Benda yang terakhir masuk ke dalam stack akan menjadi yang pertama keluar dari stack.

misalnya:
Terdapat stack S=(a1, a2, a3, …, an)
1. Elemen mana yang merupakan elemen terbawah.
2. Elemen mana yang merupakan elemen paling atas.
3. Elemen mana yang akan dikeluarkan.
4. Elemen mana yang paling akhir dikeluarkan.

KARAKTERISTIK STACK
• Elemen stack yaitu item-item data di elemen stack.
• Top (elemen puncak dari stack)
• Jumlah elemen pada stack.
• Status / kondisi stack.

KONDISI STACK
Kondisi stack yang perlu diperhatikan adalah :
1. Penuh: bila elemen stack mencapai kapasitas maksimum. Pada kondisi ini tidak mungkin dilakukan penambahan ke stack. Penambahan elemen menyebabkan kondisi kesalahan overflow.
2. Kosong: bila tidak ada elemen di stack. Pada kondisi ini, tidak mungkin dilakukan pengambilan elemen dari stack. Pengambilan elemen menyebabkan kondisi kesalahan underflow.

STACK REPRESENTASI STATIS
• Biasanya diimplementasikan dengan menggunakan array.
• Karena itu, stack dengan representasi statis dapat mengalami kondisi elemen penuh.

STACK REPRESENTASI DINAMIS
• Biasanya diimplementasikan dengan menggunakan pointer yang menunjuk pada elemen-elemen yang dialokasikan pada memori.
• Elemen ditambahkan akan menggunakan penambahan elemen pada awal stack (addfirst).
• Saat pengambilan atau penghapusan elemen menggunakan penghapusan di awal stack (delfirst).

OPERATOR-OPERATOR DI DALAM STACK

OPERASI PUSH
Adalah operasi menambahkan elemen baru pada sebuah stack. Aturan penambahan stack: Sebagai kondisi awal ada sebuah stack yang telah memiliki beberapa elemen dengan elemen paling atas sebagai top. Dibuat sebuah elemen baru yang akan dimasukkan ke dalam stack.
• Elemen baru dimasukkan ke dalam stack.
• Penunjuk top pada stack diubah menunjuk ke elemen yang baru saja ditambahkan.

OPERASI POP
Adalah operasi mengambil sebuah elemen dari sebuah stack. Aturan mengambil sebuah elemen dari sebuah stack adalah sebagai berikut :
• Sebagai kondisi awal ada sebuah stack yang telah memiliki beberapa elemen dengan elemen paling atas sebagai top.
• Penunjuk top diubah menjadi menunjuk elemen di bawah elemen atas.
• Elemen atas diambil dari stack.

CREATE
Operator ini berfungsi untuk membuat sebuah stack kosong.

ISEMPTY
Operator ini berfungsi untuk menentukan apakah suatu stack adalah stack kosong. Operasinya akan bernilai boolean, dengan definisi sebagai berikut :
ISEMPTY(S) = true, jika S adalah stack kosong = false, jika S bukan stack kosong atau ISEMPTY(S) = true, jika (S) = NULL = false, jika (S) = 1
Catatan : ISEMPTY(CREATE(S)) = true.

ISFULL
Operator ini berfungsi untuk menentukan apakah suatu stack adalah stack penuh. Operasinya akan bernilai boolean, dengan definisi sebagai berikut :
ISFULL(S) = true, jika S adalah stack penuh = false, jika S bukan stack penuh
Catatan : ISEMPTY(CREATE(S)) = true.

PENGGUNAAN STACK
• Dalam dunia komputer, penggunaan stack (tumpukan) merupakan suatu hal yang umum digunakan seperti untuk penentuan alamat memory, penempatan ruang data dan aplikasi lain.
• Aplikasi stack juga digunakan untuk berbagai macam keperluan seperti pengujian kalimat palindrome, penguji tanda kurung (matching parentheses), dan juga berfungsi sebagai konversi dari notasi infix menjadi notasi postfix.
• Sebuah kompilator mempunyai tugas, salah satu di antaranya adalah menyelidiki apakah Pemrogram telah dengan cermat mengikuti aturan tata bahasa, atau sintaks dari bahasa pemrograman yang bersangkutan.
• Misalnya untuk parantheses kiri (tanda kurung buka) yang diberikan, harus dipastikan adanya parantheses kanan (tanda kurung tutup) yang bersangkutan.

MATCHING PARENTHESES
Proses ini dilakukan compiler untuk memeriksa kelengkapan tanda kurung yang terdapat pada suatu ekspresi aritmetik. Sedangkan stack di sini digunakan sebagai tempat prosesnya. Algoritma yang digunakan adalah :
1. Elemen-elemen suatu ekspresi aritmetik (string) di-Scan dari kiri ke kanan.
2. Jika ditemukan simbol "(" atau "Left parenthesis", maka simbol tersebut di-push ke dalam stack.
3. Jika ditemukan simbol ")" atau "Right parenthesis", maka isi stack diperiksa.
• Jika stack kosong terjadi kesalahan. berarti : ada simbol "(", tetapi tidak ada simbol ")" yang seharusnya mendahului.
• Jika stack tidak kosong artinya ada pasangannya dan langsung di-POP keluar stack.

INTERPRETER POSTFIX
• Contoh lain penggunaan stack adalah pemeriksaan dan eksekusi ekpresi postfix.
• Ekspresi postfix merupakan ekpresi dengan aturan L R B dengan L adalah operand kiri, R operand kanan dan B adalah operatornya.
• Ekspresi yang kita biasa gunakan sehari-hari adalah ekspresi infix dengan aturan L B R. Contoh, jika ekspresi infixnya "6*7-2" maka ekspresi postfixnya adalah "6 7 * 2 -".

NOTASI INFIX DAN POSTFIX
• Suatu perhitungan aritmatika biasanya berhubungan dengan operand dan operator. Operand merupakan suatu karakter atau elemen yang nilainya dioperasikan dengan bantuan suatu operator untuk menghasilkan suatu solusi.
• Misalkan jika diberikan suatu ekspresi aritmatika 2 * 3, maka elemen ‘dua’ dan elemen ‘tiga’ merupakan operand dari ekspresi tersebut dan elemen ‘*’ merupakan operator perkalian atas dua operand yang menghasilkan suatu solusi.
• Dalam penggunaannya, dalam kehidupan sehari-hari notasi infix merupakan notasi aritmatika yang paling banyak digunakan untuk mengekspresikan suatu perhitungan artimatik dibanding dengan dua notasi yang lain.
• Akan tetapi notasi Postfix merupakan notasi yang digunakan oleh mesin kompilasi pada komputer dengan maksud untuk mempermudah proses pengkodean, sehingga mesin kompilasi membutuhkan stack untuk proses translasi ekspresi tersebut.

NOTASI POSTFIX
Bentuk aplikasi stack yang lain adalah mengubah suatu ekspresi aritmatik (string) ke dalam notasi postfix. Notasi postfix ini digunakan oleh compiler untuk menyatakan suatu ekspresi aritmatik dalam bahasa tingkat tinggi (high level language). Stack digunakan oleh compiler untuk mentransformasikan ekspresi aritmatik menjadi suatu ekspresi dalam bentuk/notasi postfix.
Contoh :
Misal diberikan ekspresi aritmatik : A + B ; Maka bentuknya dalam notasi postfix menjadi : AB+
Urutan (prioritas) dari operator adalah :
• Perpangkatan (^)
• Perkalian (*) atau Pembagian (/)
• Penjumlahan (+) atau Pengurangan (-)


ATURAN DALAM PROSES TRANSFORMASI KE POSTFIX
• Ekspresi aritmatik yang diberikan di- "Scan" dari kiri ke kanan.
• Bila simbol yang di-scan adalah "(", maka simbol tersebut di push ke dalam stack.
• Bila simbol yang di-scan adalah ")", maka seluruh isi stack di pop keluar mulai dari simbol "()" yang pertama ditemukan dalam stack.
• Bila simbol adalah operator, maka dilakukan perbandingan dulu dengan simbol (operator) yang berada pada posisi top dalam stack:Jika derajatnya setara atau lebih rendah dari simbol yang berada pada posisi top, maka top stack di-pop keluar sebagai output dan simbol yang baru di-push ke dalam stack.
• Jika derajatnya lebih tinggi dari simbol yang berada pada posisi top, maka simbol (operator) yang di-scan tersebut di-push ke dalam stack.
• Bila simbol yang di-scan adalah operand, maka simbol tersebut langsung sebagai output. Bila simbol adalah ";" maka seluruh isi stack di-pop sebagai output. Jika derajatnya lebih tinggi dari simbol yang berada pada posisi top, maka simbol (operator) yang di-scan tersebut di-push ke dalam stack.
• Bila simbol yang di-scan adalah operand, maka simbol tersebut langsung sebagai output. Bila simbol adalah ";" maka seluruh isi stack di-pop sebagai output.

CONTOH :
3 + 2 * 5 = 325*+ (A + B) * (C – D) / E; = AB+*CD-E/


Inisialisasi
void inisialisasi ()
{
tumpuk.top = -1
}

• Pada mulanya isi top dengan -1, karena array dalam C/C++ dimulai dari 0, berarti stack adalah KOSONG
• TOP adalah variabel penanda dalam STACK yang menunjukkan elemen teratas Stack.
• TOP of STACK akan selalu bergerak hingga mencapai MAX of STACK sehingga menyebabkan stack PENUH

Fungsi IsEmpty
int IsEmpty ()
{
if tumpuk.top == -1
return 1;
else
return 0;
}

• Digunakan untuk memeriksa apakah stack masih dalam kondisi kosong
• Dengan cara memeriksa TOP of STACK. Jika TOP masih = -1 maka berarti stack masih kosong

Fungsi IsFull
• Digunakan untuk memeriksa apakah kondisi stack sudah penuh
• Dengan cara memeriksa TOP of Stack. Jika TOP of STACK = MAX_STACK-1 maka FULL (Penuh). Jika TOP of STACK MAX_STACK-1 maka belum penuh

Fungsi PUSH
Digunakan untuk memasukkan elemen ke dalam stack dan selalu menjadi elemen teratas stack Dengan cara :
1. Menambah satu (increment) nilai TOP of STACK setiap ada penambahan elemen stack selama stack masih belum penuh
2. Isikan nilai baru ke stack berdasarkan indeks TOP of STACK setelah ditambah satu (diincrement)

Fungsi POP
Digunakan untuk menghapus elemen yang berada pada posisi paling atas dari stack. Dengan cara :
1. Ambil dahulu nilai elemen teratas stack dengan mengakses TOP of STACK.
2. Tampilkan nilai yang akan diambil.
3. Lakukan decrement nilai TOP of STACK sehingga jumlah elemen stack berkurang 1

Fungsi CLEAR
Digunakan untuk mengosongkan stack / membuat stack hampa sehingga Top pada Stack berada kembali di posisi Top = -1
void clear ()
{ t
umpuk.data=tumpuk.top=-1
printf(“Data clear”);
}

Penulis Muhamad Dzikrulloh